package offer.nowcoder.array;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * @author DengYuan2
 * @create 2021-02-18 21:10
 */
public class n_59 {
    public static void main(String[] args) {
        n_59 n = new n_59();
        int[] arr={2,3,4,2,6,2,5,1};
        int size=3;
        ArrayList<Integer> res = n.maxInWindows(arr, size);
        System.out.println(res);
    }

    /**
     * 看了大神写的，用得大顶堆
     * @param num
     * @param size
     * @return
     */
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if (size>num.length || size<1){
            return list;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
        for (int i = 0; i < size; i++) {
            queue.offer(num[i]);
        }
        for (int i = size; i < num.length; i++) {
            list.add(queue.peek());
            queue.remove(num[i-size]);
            queue.offer(num[i]);
        }
        list.add(queue.peek());
        return list;
    }
}
